{
LANG : PASCAL
PROB : ditch
}

program DITCH;
const
  fi = 'ditch.in';
  fo = 'ditch.out';
  max = 200;
var
  c, f : array[1..max, 1..max] of longint;
  trace : array[1..max] of integer;
  n, m, res : longint;

procedure inp;
var
  i, u, v, k : longint;
begin
  read(m, n);
  fillchar(c, sizeof(c), 0);
  for i := 1 to m do
  begin
    read(u, v, k);
    inc(c[u, v], k);
  end;
end;

function timthayduong : boolean;
var
  q : array[1..max] of integer;
  l, r, u, v : integer;
begin
  l := 1;
  r := 1;
  q[1] := 1;
  fillchar(trace, sizeof(trace), 0);
  while l <= r do
  begin
    u := q[l];
    inc(l);
    for v := 1 to n do
      if (trace[v] = 0) and (c[u, v] > f[u, v]) then
      begin
        trace[v] := u;
        if v = n then
        begin
          timthayduong := true;
          exit;
        end;
        inc(r);
        q[r] := v;
      end;
  end;
  timthayduong := false;
end;

procedure tangluong;
var
  u, v, delta : longint;
begin
  v := n;
  delta := maxlongint;
  repeat
    u := trace[v];
    if delta > c[u, v] - f[u, v] then delta := c[u, v] - f[u, v];
    v := u;
  until v = 1;
  inc(res, delta);

  v := n;
  repeat
    u := trace[v];
    inc(f[u, v], delta);
    dec(f[v, u], delta);
    v := u;
  until v = 1;
end;

procedure process;
begin
  res := 0;
  while timthayduong do tangluong;
end;

procedure out;
begin
  writeln(res);
end;

begin
  assign(input, fi); reset(input);
  assign(output, fo); rewrite(output);

  inp;
  process;
  out;

  close(output);
  close(input);
end.